package problem494;

//494.目标和
//https://leetcode.cn/problems/target-sum/

class Solution {
    int count = 0, sum = 0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, target, 0);
        return count;
    }
    public void dfs(int[] nums, int target, int pos) {
        if(pos == nums.length) {
            if(sum == target) count ++;
            return;
        }
        
        //+
        sum += nums[pos];
        dfs(nums, target, pos+1);
        sum -= nums[pos];
        
        //-
        sum -= nums[pos];
        dfs(nums, target, pos+1);
        sum += nums[pos];
    }
}